#include<bits/stdc++.h>
using namespace std;



class Solution
{
private:
    /* data */
public:
    bool canPartitionKSubsets(vector<int>& nums,int k){
        long long sum=0;
        for(int i=0;i<nums.size();++i){
            sum+=nums[i];
        }
        if(sum%k!=0){
            return false;
        }
        sum = sum/k;
        vector<int> dp(sum+1,0);
        for(int i=0;i<nums.size();++i){
            for(int j=sum;j>=nums[i];--j){
                dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[sum]==sum;
    }
};

int main(int argc, char const *argv[])
{
    vector<int> nums={4, 3, 2, 3, 5, 2, 1};
    int k=4;
    Solution s;
    cout<<s.canPartitionKSubsets(nums,k)<<endl;
    return 0;
}
